from collections import defaultdict
from typing import List


class Solution:
    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:
        if n <= 4:
            return [1, 2, 3, 4][:n]
        # 用二进制方式记录相邻有哪些花园
        garden = [0] * n
        for i in range(n):
            garden[i] = set()
        for [i, j] in paths:
            garden[i - 1].add(j - 1)
            garden[j - 1].add(i - 1)
        
        ans = [0] * n

        for i in range(n):
            # 记录相邻的花园已种哪些花
            usedFlowers = set()
            for j in garden[i]:
                usedFlowers.add(ans[j])
            for j in range(1, 5):
                if j not in usedFlowers:
                    ans[i] = j
                    break
        return ans


class Solution2:
    '''此方法比方法1更快'''
    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:
        graph = defaultdict(list)
        for i,j in paths:
            graph[i].append(j)
            graph[j].append(i)
        ans = [0]*(n+1)
        for k,v in graph.items():
            if not ans[k]:
                visited = [1]*5
                for j in v:
                    visited[ans[j]] = 0
                for i in range(1,5):
                    if visited[i] == 1:
                        ans[k] = i
                        break
        for i,j in enumerate(ans):
            if j == 0:
                ans[i] = 1
        return ans[1:]
